package com.yang;

/**
 * @author yds
 * @program yds-hash-map
 * @description 1.7 数组+链表
 *              1.8 数组+链表+红黑树
 * @create 2021-01-26 14:02
 **/
public class HashMap<K,V> implements Map<K,V>{

    private Entry<K,V> table[]=null; //每一个hash桶里面的链表

    int size=0;

    public HashMap(){
        this.table=new Entry[16];
    }

    /**
     * 通过key hash算法算出hash值
     * index下标数组 当前下标对象
     * 判断当前对象是否为空
     * 为空则存储
     * 不为空，hash冲突，需要用到next链表
     * 返回当前节点
     * @param k
     * @param v
     * @return
     */
    public V put(K k, V v) {
        int index=hash(k);
        Entry<K,V> entry=table[index];
        if(entry==null){
            //
            table[index]= new Entry(k, v, index, null);
            size++;
        }else{
            //hash冲突
            table[index]=new Entry(k, v, index, entry);
        }

        return  table[index].getValue();
    }

    /**
     * 自定义简单hash
     * @param k
     * @return
     */
    private int hash(K k) {
        int index=k.hashCode()%16;
        return index>=0?index:-index;
    }

    /**
     * 通过key获取hash下标
     * 判断是否为空，为空返回null
     * 不为空，则判断是否相等
     * 判断next是否为空，如果不为空
     * 判断是否相等，直到相等
     * @param k
     * @return
     */
    public V get(K k) {
        if(size==0){
            return null;
        }
        int index=hash(k);
        if(table[index]==null){
            return null;
        }
        Entry<K,V> entry=findValue(table[index],k);
        return entry==null?null:entry.getValue();
    }

    /**
     * 使用递归
     * @param entry
     * @param k
     * @return
     */
    private Entry<K,V> findValue(Entry<K,V> entry, K k) {
        if(k.equals(entry.getKey())||k==entry.getKey()){
           return entry;
        }else{
            if(entry.next!=null){
                return  findValue(entry.next, k);
            }
        }
        return null;
    }

    public int size() {
        return size++;
    }

    //链表实现
    class Entry<K,V> implements Map.Entry<K,V>{
        K k; //key
        V v; //value
        int hash; //hash下标
        Entry<K,V> next; //下一个数组节点

        public Entry(K k, V v, int hash, Entry<K, V> next) {
            this.k = k;
            this.v = v;
            this.hash = hash;
            this.next = next;
        }

        public K getKey() {
            return k;
        }

        public V getValue() {
            return v;
        }
    }
}